package leetcode.code0123;

/**
 *
 * @author CaoYu
 * @date 2021年11月26日
 * @description
 */
public class Solution extends Solution123 {

	@Override
	public int maxProfit(int[] prices) {
		int len = prices.length;
		int max = 0;
		int[] maxs = new int[len + 1];
		for (int i = len - 1; i >= 0; i--) {
			int price = prices[i];
			maxs[i] = Math.max(maxs[i + 1], max - price);// [i,len-1]最大差值
			max = Math.max(max, price);// [i,len-1]位置右侧的最大值
		}
		int min = Integer.MAX_VALUE;
		max = 0;
		for (int i = 0; i < len; i++) {
			int price = prices[i];
			min = Math.min(min, price);// [0,i]最小值
			max = Math.max(max, price - min + maxs[i + 1]);// [0,i]最大值 + [i+1,len-1]最大值
		}
		return max;
	}

	private int f(int[] prices, int start, int len) {
		int min = Integer.MAX_VALUE;
		int max = 0;
		for (int i = start; i < len; i++) {
			int price = prices[i];
			min = Math.min(min, price);
			max = Math.max(max, price - min);
		}
		return max;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
